class LRUCache:

    def __init__(self, capacity: int):
        self.max_num = capacity
        self.__cache = {}
        self._keys = []

    def get(self, key: int) -> int:
        if key in self._keys:
            self._keys.remove(key)
            self._keys.append(key)
        return self.__cache.get(key, -1)

    def put(self, key: int, value: int) -> None:
        if key in self._keys:
            self._keys.remove(key)
        elif len(self._keys) >= self.max_num:
            _key = self._keys.pop(0)
            self.__cache.pop(_key)
        
        self._keys.append(key)
        self.__cache[key] = value        




# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)